package com.otherTest.conceitHashMap;

/**
 * 第二次实现hashMap
 * <p>
 * JDK1.8 HashMap是数组+链表+红黑树实现的
 * JDK1.7 HashMap是数组+链表实现的
 * <p>
 * JDK1.8 HashMap扩容机制说明:
 * 1.如果桶中entry的数量小于TREEIFY_THRESHOLD不会转化成树形结构存储
 * 2.如果桶中entry的数量大于TREEIFY_THRESHOLD ，但是桶的数量小于MIN_TREEIFY_CAPACITY 则依然使用链表结构进行存储，此时会对HashMap进行扩容
 * 3.如果桶的数量大于了MIN_TREEIFY_CAPACITY ，则会进行树化。
 * 4.如果其他桶中entry的数量没有超过TREEIFY_THRESHOLD，则用链表存储，如果超过TREEIFY_THRESHOLD ，则用树形存储。
 * <p>
 * 名词解释:
 * 1.每个Map数组中的entry对象即为桶,源码中hashMap的内部实现类名为node,实现map的Entry的内部接口
 * 2.每个entry中对应的key,value对 即为bin,箱子
 * 3.size为该hashMap总所有bin的数量
 *
 * @author Conceit
 * 2017-09-05 添加方法 SecondTimeHashMapImpl
 * 2017-09-05 添加方法 get
 * 2017-09-05 添加方法 put
 * 2017-09-05 添加方法 size
 * 2017-09-05 添加方法 getKey
 * 2017-09-05 添加方法 getValue
 * 2017-09-05 添加方法 setValue
 * 2017-09-05 添加方法 equals
 * 2017-09-05 添加方法 hashCode
 * 2017-09-12 添加方法 hash
 * 2017-09-12 添加方法 tableSizeFor
 * @since 1.0.0, 2017/9/5
 */
public class SecondTimeHashMapImpl<K, V> implements ISecondTimeHashMap<K, V> {


    //哈希表的最小树形化容量
    //当哈希表中的容量大于这个值时，表中的桶才能进行树形化
    //否则桶内元素太多时会扩容，而不是树形化
    //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
    static final int MIN_TREEIFY_CAPACITY = 64;
    //一个树的链表还原阈值
    //当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
    //这个值应该比上面那个小，至少为 6，避免频繁转换
    static final int UNTREEIFY_THRESHOLD = 6;
    //形成树结构的阈值
    private static final int TREEIFY_THRESHOLD = 8;
    //定义默认hashMap初始长度,即桶的数量,容量都是2的幂
    private static int DEFAULT_INITIAL_CAPACITY = 16;
    //定义默认增量因子
    //计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity
    private static float DEFAULT_LOAD_FACTOR = 0.75F;
    //定义hashMap最长容量,2的30次方
    private static int MAXIMUM_CAPACITY = 1073741824;

    float loadFactor;
    //定义默认entryArray
    private Node<K, V>[] table = null;
    //当前的阈值,即当前hashMap的size超过此值会启动扩容
    private int thresHold;

    /**
     * 定义无参构造方法
     * 使用默认长度和增量因子
     *
     * @throws IllegalArgumentException 非法参数
     */
    public SecondTimeHashMapImpl() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }


    /**
     * 构造方法2
     * initialCapacity会调用tableSizeFor方法返回一个比给定整数大且最接近的2的幂次方整数
     * 因为痛的数量都是2的幂次方
     *
     * @param initialCapacity 初始化桶数量
     * @param loadFactor      扩容因子
     * @throws IllegalArgumentException 非法参数
     */
    public SecondTimeHashMapImpl(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("定义的hashMap初始长度有误" + initialCapacity);
        }
        //超过最大的值，则将值重新赋值
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        if (loadFactor < 0) {
            throw new IllegalArgumentException("定义的hashMap增量因子有误" + loadFactor);
        }
        //将传入的装载因子进行赋值
        this.loadFactor = loadFactor;
        //扩容阈值 此值为动态值,计算出传入的扩容形参的阈值
        this.thresHold = tableSizeFor(initialCapacity);

    }

    /**
     * 构造方法3
     *
     * @param initialCapacity
     * @return SecondTimeHashMapImpl
     */

    public SecondTimeHashMapImpl(int initialCapacity) {

    }

    /**
     * 夭寿啦
     * 返回一个比给定整数大且最接近的2的幂次方整数
     * 如给定10，返回2的4次方16.
     * <p>
     * 找到大于等于initialCapacity的最小的2的幂
     * （initialCapacity如果就是2的幂，则返回的还是这个数）。
     * 二进制位运算符
     * <p>
     * 效率高  难理解
     * <p>
     * var0 - 1是为了防止如果cap已经是2的幂,又没有执行这个减1操作
     * 则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍
     * <p>
     * 本方法实际就是计算桶数量下一次的扩容size
     *
     * @param var0 桶数量
     * @return 返回类型
     */
    private int tableSizeFor(int var0) {

        int var1 = var0 - 1;
        //位运算符
        var1 |= var1 >>> 1;
        var1 |= var1 >>> 2;
        var1 |= var1 >>> 4;
        var1 |= var1 >>> 8;
        var1 |= var1 >>> 16;


        //最终值是否小于0小于0 则返回1
        if (var1 < 0) {
            return 1;
        }
        //最终值大于等于最高容量则返回会搞容量否则返回原值
        return var1 >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : var1 + 1;
    }


    /**
     * 计算该key的hash值
     * 源码中若参数为null则返回0
     * 本例修改计算hash的方式
     *
     * @param var1 Object对象
     * @return 返回类型 int 该key的hash散列值
     */
    private int hash(Object var1) {
        int hashCode;
        hashCode = var1.hashCode();
        // 二进制运算  ^异或运算符  无符号右移(>>>)
        hashCode = hashCode ^ (hashCode >>> 20) ^ (hashCode >>> 12);
        hashCode = hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
        return hashCode;
    }

    /**
     * 查询方法
     *
     * @param var1 map对应的key
     * @retrue v
     */
    public V get(Object var1) {

        return null;
    }

    /**
     * 保存方法
     *
     * @param var1 key
     * @param var2 value
     */
    public V put(K var1, V var2) {
        return null;
    }

    /**
     * 获取map总size
     * size表示HashMap中存放KV的数量（为链表和树中的KV的总和）
     */
    public int size() {

        return 0;
    }


    /**
     * 实现公共内部类entry
     */
    class Node<K, V> implements ISecondTimeHashMap.Entry<K, V> {
        /**
         * 获取key
         */
        public K getKey() {
            return null;
        }

        /**
         * 获取value
         */
        public V getValue() {
            return null;
        }

        /**
         * 设置value
         */
        public V setValue() {
            return null;
        }

        /**
         * 重写equals
         */
        public boolean equals(Object var1) {
            return false;
        }

        /**
         * 重写hashCode
         */
        public int hashCode() {
            return 0;
        }

    }

}
